package heap;

import org.junit.Test;

import java.util.Comparator;
import java.util.PriorityQueue;

//求解数据流的中位数问题
public class LeetCode_LCR160 {

    private static PriorityQueue<Integer> maxHeap;
    private static PriorityQueue<Integer> minHeap;

    private static class MaxComparator implements Comparator<Integer> {

        @Override
        public int compare(Integer o1, Integer o2) {
            return o2-o1;
        }
    }

    private static class MinComparator implements Comparator<Integer> {

        @Override
        public int compare(Integer o1, Integer o2) {
            return o1-o2;
        }
    }


    //初始化大根堆，小根堆
    public void init(){
        maxHeap = new PriorityQueue<>(new MaxComparator());
        minHeap = new PriorityQueue<>(new MinComparator());
    }

    // 添加数值
    public void addNum(int num) {
        // 1.初始情况，直接进入大根堆
        if (maxHeap.size() == 0){
            maxHeap.add(num);
            return;
        }
        // 2. 插入数值，通过判断和大根堆堆顶的大小关系，决定插入到大根堆还是小根堆
        if (num > maxHeap.peek()){
            //2.1 判断和小根堆的堆顶的大小关系
            if (minHeap.size()>0 && num > minHeap.peek()){
                minHeap.add(num);
            }else {
                maxHeap.add(num);
            }
        }else{
            maxHeap.add(num);
        }
        // 3. 调整堆
        if (Math.abs(maxHeap.size() - minHeap.size())==2 ){
            if (maxHeap.size() > minHeap.size()){
                int temp = maxHeap.poll();
                minHeap.add(temp);
            }else{
                int temp = minHeap.poll();
                maxHeap.add(temp);
            }
        }
    }

    // 返回中位数
    public double findMedian() {

        if ((maxHeap.size() + minHeap.size()) % 2 == 1) {

            return (maxHeap.size() > minHeap.size())?(double) maxHeap.peek():(double) minHeap.peek();
        }else {
            return (double) (maxHeap.peek() + minHeap.peek()) / 2;
        }

    }

    @Test
    public void test(){
        LeetCode_LCR160 test = new LeetCode_LCR160();
        test.init();
        test.addNum(1);
        System.out.println(test.findMedian());
//        test.addNum(2);
//        System.out.println(test.findMedian());
//        test.addNum(3);
//        System.out.println(test.findMedian());

    }




}
